The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventor, to the extent it is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure.
In order to facilitate the printing of images in a printing device, an image having continuous tones (also referred to as a “continuous tone image” or a “contone image”) is often converted into an image having halftones. An example of a halftone image is an image whose pixels are binary, having one of two colors such as either black or white.
For example, a grayscale image is a contone image whose pixels range continuously from white to black, with various intermediate levels of gray. Many printers, however, are capable only of printing black dots, and are not capable of printing gray dots. Instead, such printers represent shades of gray by printing different densities of black dots. Thus, a lighter area has a lower density of black dots, and a darker area has a higher density of black dots.
Color printing is often based on a source image that comprises multiple contone images corresponding respectively to different color planes such as cyan, magenta, yellow, and black (CMYK). Before being printed, these contone images must be converted to halftone images.
Color halftoning can be performed using various existing techniques. As a simple example, the intensity of each source pixel can be compared to an intermediate intensity threshold, with pixels exceeding the intensity threshold being set to black, and pixels not exceeding the intensity threshold being set to white.
A more complex use of thresholds involves a so-called dither array, in a process referred to as amplitude-modulated (AM) or frequency-modulated (FM) digital halftoning. A dither array is a two-dimensional matrix of intensity thresholds that is tiled over the source image. For any particular source pixel, the coinciding value of the dither array is used as an intensity threshold. This has the effect of creating differently sized clusters of dots. The dither array is typically small relative to the source image, and comprises consecutive intensity thresholds arranged in a specific pattern relative to the array. In amplitude-modulated halftoning, the intensity thresholds are arranged consecutively along a path that spirals outwardly from the array's center. In frequency-modulated halftoning, the consecutive intensity thresholds are dispersed as much as possible within the array.
Error diffusion is another technique used in halftoning. Error diffusion is based on the recognition that there is a known quantization error whenever converting a continuous value to a binary value. Error diffusion keeps track of the quantization error and distributes the quantization error to neighboring pixels as processing proceeds through the pixels of an image. Thus, the binary value of each halftone pixel is determined both by the original value of the pixel and by any error that has accumulated during the processing of previous pixels. Floyd-Steinberg dithering is an example of a widely used error diffusion implementation.
Refinements to the halftoning techniques described above tend to focus on the reduction of unwanted discernable patterns that sometimes results from these techniques. As an example, some implementations utilize so-called blue-noise in conjunction with error diffusion to reduce the appearance of unnatural patterns in halftone images. Another technique is to increase the area over which accumulated quantization errors are distributed, or to otherwise manipulate the way in which errors are diffused to neighboring pixels.
Color halftoning introduces additional challenges as compared to the halftoning of monochrome images having only a single color plane. Many color halftoning methods process each color plane independently, without addressing the potential interaction of the different color planes with each other. Other methods account for such interaction, but only through expensive and performance-reducing post-processing. Furthermore, current methods often require serpentine scanning of the image in a manner that is not coherent with pen geometry, and therefore require large memory buffers.